package com.icehand.utils.matcher;

import org.apache.commons.lang3.StringUtils;

/**
 * KMP搜索算法
 * 匹配到了字符：后移位数 = 已匹配的字符数 - 对应的部分匹配值
 * 未匹配到 ： 后移一位
 * Created by icehand on 2017/5/3.
 */
public class KMP implements Matcher{
	private String text;
	private String pattern;

	private int[] next;

	private int countCommon(char[] p ,int index){
		int result = 0;

		if(index == 0){
			return result;
		}

		int[] tmp = new int[index+1];
		for (int i = 1; i < index+1; i++) {
			if(tmp[i-1] !=0 && p[tmp[i-1]] == p[i]){
				//如果之前的匹配成功
				tmp[i] = tmp[i-1]+1;
			}else if(p[0] == p[i]){
				tmp[i] = 1;
			}
		}

		result = tmp[index];

		return result;
	}

	/**
	 * 计算匹配表
	 * @return int[]
	 */
	private int[] getNext(){
		if(StringUtils.isEmpty(pattern)){
			return new int[1];
		}

		char[] p = pattern.toCharArray();
		int [] result = new int[pattern.length()];
		int j = 0;
		while(j < pattern.length()){
			result[j] = countCommon(p,j);
			j++;
		}
		return result;
	}

	public KMP(String text , String pattern){
		this.text = text;
		this.pattern = pattern;
		next = getNext();
	}

	@Override
	public int match(){
		if(StringUtils.isEmpty(text) || StringUtils.isEmpty(pattern)){
			return -1;
		}

		int i = 0;//text
		int j = 0;//pattern

		while(i < text.length() && j < pattern.length()){
			if(text.charAt(i) == pattern.charAt(j)){
				i++;
				j++;
			}else if(j==0){
				i =i +1;
				j = 0;
			}else{
				i = i-next[j];
				j = 0;
			}

			//匹配成功
			if(j==pattern.length()){
				return i-j;
			}
		}

		return -1;
	}

	@Override
	public boolean contains(){
		return match() != -1;
	}

	public static void main(String[] args){
		long start = System.currentTimeMillis();
		String text = "BBC ABCDAB ABCDABDABDE";
		String pattern = " ";
		KMP kmp = new KMP(text,pattern);
		System.out.print(kmp.match());
		System.out.print(System.currentTimeMillis()-start);
	}
}
